package q1089_duplicateZeros;

public class Solution_2 {
    /*
    solution1的问题在于时间复杂度
    如果出现多次0 就意味着每次都要从最后开始重新读取数组进行复写
    那么此时为了降低时间复杂度
    就需要采用不同的方式
    首先我们假定一个栈top 它的容量是数组的长度
    首先遍历一次数组，每次遇到非0 top + 1 如果是0 则 + 2
    用这样的方式我们可以得到复写之后数组的最后一个数字是什么
     */
    public void duplicateZeros(int[] arr) {
        int n = arr.length;
        int top = 0;
        int i = -1;
        while (top < n) {
            i++;
            if (arr[i] != 0) {
                top++;
            } else {
                top += 2;
            }
        }
        int j = n - 1;
        if (top == n + 1) {
            arr[j] = 0;
            j--;
            i--;
        }
        /*
        然后开始从后往前填
         */
        while (j >= 0) {
            arr[j] = arr[i];
            j--;
            if (arr[i] == 0) {
                arr[j] = arr[i];
                j--;
            }
            i--;
        }
    }

}
